package com.shixianjun.sort;

public class _5_归并排序 implements Sortable{

    public static void main(String[] args) {
        SortableElement[] arr = {
                new SortableElement(1, 5),
                new SortableElement(1, 10),
                new SortableElement(1, 6),
                new SortableElement(1, 7),
                new SortableElement(1, 2),
                new SortableElement(1, 17),
                new SortableElement(1, 07),
                new SortableElement(1, 07),
                new SortableElement(1, 20),
                new SortableElement(1, 13),
        };

//        05 10 06 07 02 17 07 07 20 13
        new _5_归并排序().sort(arr);
        SortableElement.printSortableElementArray("arr", arr);
    }

    @Override
    public void sort(SortableElement[] arr) {
        sort1(arr, 0, arr.length - 1);
    }

    public void sort1(SortableElement[] arr, int begin, int end) {
        if (arr.length <= 1) return;
        if (begin < 0 || end >= arr.length) return;
        if (begin == end) return;

        int mid = (end - begin) / 2 + begin;

        sort1(arr, begin, mid);
        sort1(arr, mid +1, end);
        merge(arr, begin, end);
    }

    public void merge(SortableElement[] arr, int begin, int end) {

        int mid = (end - begin) / 2 + begin;
        int index = 0, first = begin, second = mid + 1;
        SortableElement[] temp = new SortableElement[end - begin + 1];

        while (first <= mid && second <= end) {
            temp[index++] = arr[first].value <= arr[second].value ? arr[first++] : arr[second++];
        }

        while (first <= mid) temp[index++] = arr[first++];
        while (second <= end) temp[index++] = arr[second++];

        for (int i = 0; i < temp.length; i++) arr[begin + i] = temp[i];
    }
}
